The present invention relates to link state routing. More specifically, the present invention relates to generating network topology mapping with two-way connectivity checking.
Generally, a network topology map is used to generate routing tables at specific network nodes. The routing tables allow the network nodes to determine the appropriate “next hop” of a packet. In order to generate a network topology map at a specific node, various network topology information can be transmitted from other network nodes. Each network node can create a link state packet containing information about the distance, delay, or cost to each of its neighbors. Distance, delay, or cost all refer to some metric associated with the link between nodes. The packet is then transmitted to all of the network nodes in the network. As one of skill in the art would appreciate, a network node receiving link state packets from the other nodes in a network can apply Dijkstra's algorithm to generate a network topology map for building a routing table.
The network node receiving link state packets from the other nodes is termed the root node. Each link state packet is processed based on distance from the root node. As the link state packet of a current node is processed, the links between the current node and each of the current node's neighbors is checked for two-way connectivity. The two-way connectivity check allows the verification of a particular link. More specifically, the two-way connectivity check allows a router to ensure that two nodes both indicate they have a link to each other.
As one of skill in the art would appreciate, typical two-way connectivity checking requires more than one traversal of link state packets. Because of the volume of nodes in a network, the additional traversal of a link state packet consumes valuable time and resources.
Currently available techniques for generating a network topology map with two-way connectivity checking for building a routing table in a network node connected to a network have significant disadvantages with regard to time and processing resources. It is therefore desirable to provide a system for generating a network topology map with two-way connectivity checking that exhibits improved characteristics as compared to conventional techniques.